// 分成k份的最大乘积
// 一个数字n一定要分成k份，得到的乘积尽量大是多少
// 数字n和k，可能非常大，到达10^12规模
// 结果可能更大，所以返回结果对1000000007取模
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

// 剩余的数字rest拆成k份
// 返回最大乘积
// 暴力尝试一定能得到最优解
int f1(int rest, int k)
{
    if(k == 1) return rest;
    int ans = INT_MIN;
    for(int cur = 1; cur <= rest && (rest - cur) >= (k - 1); ++cur)
    {
        int curAns = cur * f1(rest - cur, k - 1);
        ans = max(ans, curAns);
    }
    return ans;
}

// 暴力递归
// 为了验证
int maxValue1(int n, int k)
{
    return f1(n, k);
}

long power(long x, int n, int mod)
{
    long ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}

// 贪心的解
// 这是最优解
// 如果结果很大，那么求余数
int maxValue2(int n, int k)
{
    int mod = 1e9 + 7;
    long a = n / k;
    int b = n % k;
    long part1 = power(a + 1, b, mod);
    long part2 = power(a, k - b, mod);
    return part1 * part2 % mod;
}

int main()
{
	// 对数器
	// 为了验证
    srand(time(nullptr));
    int N = 30;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; i++)
    {
        int n = rand() % N + 1;
        int k = rand() % n + 1;
        int ans1 = maxValue1(n, k);
        int ans2 = maxValue2(n, k);
        if(ans1 != ans2)
        {
            // 如果出错了
            // 可以增加打印行为找到一组出错的例子
            // 然后去debug
            cout << "出错了！" << endl;
        }
        if(i % 100 == 0)
        {
            cout << "(测试到第" << i << "组)" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}